package week8;

import jsjf.exceptions.EmptyCollectionException;

public class ArrayMaxHeap<T> extends ArrayBinaryTree<T> implements HeapADT<T>{
    public ArrayMaxHeap()
    {
        super();
    }

    // 根据堆的键值将指定的元素添加到该堆的适当位置。
    public void addElement(T obj)
    {
        if (count == tree.length)
            expandCapacity();

        tree[count] = obj;
        count++;
        modCount++;

        if (count > 1)
            heapifyAdd();
    }

    // 在添加节点后重新排序此堆以维护有序属性。
    private void heapifyAdd()
    {
        T temp;
        int next = count - 1;

        temp = tree[next];

        while ((next != 0) &&
                (((Comparable)temp).compareTo(tree[(next-1)/2]) > 0))
        {

            tree[next] = tree[(next-1)/2];
            next = (next-1)/2;
        }

        tree[next] = temp;
    }

    /**
     * Remove the element with the lowest value in this heap and
     * returns a reference to it. Throws an EmptyCollectionException if
     * the heap is empty.
     *
     * @return a reference to the element with the lowest value in this heap
     * @throws EmptyCollectionException if the heap is empty
     */
    public T removeMin() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        T minElement = tree[0];
        tree[0] = tree[count-1];
        heapifyRemove();
        count--;
        modCount--;
        return minElement;
    }
    public T removeMax() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

//        for (int x = 0; x < count(tree);x++)
//        {
//            System.out.print(tree[x] + " ");
//        }
        T minElement = tree[0];
        tree[0] = tree[count-1];
        heapifyRemove();
        count--;
        modCount--;


        return minElement;
    }

    private int count(T[] a)
    {
        int x = 0;
        while (a[x] != null)
        {
            x++;
        }
        return x;
    }

    /**
     * Reorders this heap to maintain the ordering property
     * after the minimum element has been removed.
     */
    private void heapifyRemove()
    {
        T temp;
        int node = 0;
        int left = 1;
        int right = 2;
        int next;

        if ((tree[left] == null) && (tree[right] == null))
            next = count;
        else if (tree[right] == null)
            next = left;
        else if (((Comparable)tree[left]).compareTo(tree[right]) > 0)
            next = left;
        else
            next = right;
        temp = tree[node];

        while ((next < count) &&
                (((Comparable)tree[next]).compareTo(temp) > 0))
        {
            tree[node] = tree[next];
            node = next;
            left = 2 * node + 1;
            right = 2 * (node + 1);
            if ((tree[left] == null) && (tree[right] == null))
                next = count;
            else if (tree[right] == null)
                next = left;
            else if (((Comparable)tree[left]).compareTo(tree[right]) > 0)
                next = left;
            else
                next = right;
        }
        tree[node] = temp;
    }

    /**
     * Returns the element with the lowest value in this heap.
     * Throws an EmptyCollectionException if the heap is empty.
     *
     * @return the element with the lowest value in this heap
     * @throws EmptyCollectionException if the heap is empty
     */
    public T findMin() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        return tree[0];
    }

    // 使用堆对指定的数组进行排序
    public void HeapSort(ArrayMaxHeap<T> temp)
    {
        T result ;
        // 将已排序的元素放回数组中
        while (!(temp.isEmpty()))
        {

            result = temp.removeMin();
            System.out.println();
            int[] y  = new int[count(tree)];
            for (int x = 0; x < count(tree);x++)
            {
                y[x] = (int) tree[x];
            }
            y[count(tree)- 1] = (int) result;

            for (int x = 0; x < y.length;x++)
            {
                System.out.print(y[x] + " ");
            }

        }

    }


}
